package daily.year2024.m11;

import java.util.HashSet;
import java.util.Set;

/**
 * No.264 丑数
 *
 * @author wjs 2024/11/8
 */
public class d7 {
    class Solution1 {
        //使用堆解决
        public int nthUglyNumber(int n) {
            long[] stack = new long[1000];
            int l = 1;
            stack[0] = 1;
            int c = 0;
            long res = 0;
            Set<Long> set = new HashSet<>();
            set.add(1L);
            while(c < n) {
                res = remove(stack,l--);
                long n2 = res*2, n3 = res*3, n5 = res*5;
                if(n2 > 0 && !set.contains(n2)) {
                    add(stack,l++,n2);
                    set.add(n2);
                }
                if(n3 > 0 && !set.contains(n3)) {
                    add(stack,l++,n3);
                    set.add(n3);
                }
                if(n5 > 0 && !set.contains(n5)) {
                    add(stack,l++,n5);
                    set.add(n5);
                }
                c++;
            }
            return (int)res;
        }

        private void swap(long[] num, int i, int j) {
            long tmp = num[i];
            num[i] = num[j];
            num[j] = tmp;
        }

        private void add(long[] stack, int l, long num) {
            stack[l] = num;
            int p = (l-1) >> 1;
            while(l != 0) {
                if(stack[l] >= stack[p]) {
                    break;
                }
                swap(stack,l,p);
                l = p;
                p = (l-1) >> 1;
            }
        }

        private long remove(long[] stack, int l) {
            long res = stack[0];
            stack[0] = stack[l-1];
            l--;
            int c = 1, p = 0;
            while(c < l) {
                if(c + 1 < l && stack[c] > stack[c+1]) {
                    c++;
                }
                if(stack[p] <= stack[c]) {
                    break;
                }
                swap(stack,p,c);
                p = c;
                c = (p << 1) + 1;
            }
            return res;
        }
    }

    class Solution2 {
        //动态规划解法
        public int nthUglyNumber(int n) {
            int[] dp = new int[n+1];
            dp[1] = 1;
            int j2 = 1, j3 = 1, j5 = 1;
            for(int i=2;i <= n;i++) {
                dp[i] = Math.min(dp[j2]*2,dp[j3]*3);
                dp[i] = Math.min(dp[i],dp[j5]*5);
                if(dp[j2]*2 == dp[i]) {
                    j2++;
                }
                if(dp[j3]*3 == dp[i]) {
                    j3++;
                }
                if(dp[j5]*5 == dp[i]) {
                    j5++;
                }
            }
            return (int)dp[n];
        }
    }
}
